<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      这题首先我们需要找到nums数组中的最长递增子序列的长度即300那道题，使用dp[i]
      再定义一个count[i]表示长度为i的数组nums的最长递增子序列的个数

      之前的状态转移方程:
      if(nums[i-1]>nums[j-1])   dp[i] = Math.max(dp[i], dp[j] + 1)
      即长度为i的最长递增子序列的长度=j从[1,i-1]的最长递增子序列的长度+1
      那count[i]如何更新呢

      在nums[i-1]>nums[j-1]的前提下，我们每次遍历j都是找递增子序列,因此如果dp[j]+1>dp[i],说明有更长的
      那么长度为j的递增子序列的个数就是长度为i的递增子序列的个数 count[i]=count[j]

      如果dp[j]+1==dp[i],说明长度一样，那么相同长度的count就多了,count[i]+=count[j]
      
      
      */
      var findNumberOfLIS = function (nums) {
        let dp = new Array(nums.length + 1).fill(1)
        let count = new Array(nums.length + 1).fill(1)
        dp[0] = 0
        count[0] = 0
        for (let i = 1; i < dp.length; i++) {
          for (let j = 1; j < i; j++) {
            if (nums[i - 1] > nums[j - 1]) {
              if (dp[j] + 1 > dp[i]) {
                count[i] = count[j]
                //dp[i]表示长度为i的最长子序列
                dp[i] = dp[j] + 1
              } else if (dp[j] + 1 == dp[i]) {
                count[i] += count[j]
              }
            }
          }
        }
        let maxLength = Math.max(...dp)
        let sum = 0
        //注意count[i]定义 长度为i的最长递增子序列的个数
        //[1,3,5,4,7] 长度为4和长度为5的最长递增子序列的长度都为4  dp[4]=dp[5]=4 因此我们需要找到对应的count然后相加
        for (let i = 1; i < count.length; i++) {
          if (dp[i] == maxLength) {
            sum += count[i]
          }
        }
        return sum
      }
      findNumberOfLIS([2, 2, 2, 2, 2])
    </script>
  </body>
</html>
